package com.cat.chapter055;

/**
 * @author cat
 * @description https://leetcode.cn/problems/shortest-subarray-with-sum-at-least-k/
 * @create 2025/7/26 15:29
 * @since JDK17
 */

public class Solution01 {
    static int N = ((int) (1e5 + 10)), h, t;
    static int[] deque = new int[N];
    static long[] sum = new long[N];
    public int shortestSubarray(int[] nums, int k) {
        h = t = 0;
        int n = nums.length, ans = n + 1;
        for (int i = 0; i < n; i++) {   // 前缀和
            sum[i + 1] = sum[i] + nums[i];
        }

        for (int i = 0; i <= n; i++) {
            while (h < t && sum[i] - sum[deque[h]] >= k) {
                ans = Math.min(ans, i - deque[h++]);
            }

            while (h < t && sum[deque[t - 1]] >= sum[i]) {   // 吐数字
                t--;
            }

            deque[t++] = i; // 进数字
        }
        return ans == n + 1 ? -1 : ans;
    }
}
